package com.javacoding.huawei;

import java.util.ArrayList;
import java.util.Scanner;

public class HJ28素数伴侣 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()){
            int n = scanner.nextInt();
            int[] tempArr = new int[n];
            for (int i = 0; i < n; i++) {
                tempArr[i] = scanner.nextInt();
            }
            ArrayList<Integer> events=new ArrayList<>();//偶数数组
            ArrayList<Integer> odds=new ArrayList<>(); //奇数数组
            for(int i=0;i<n;i++){
                if((tempArr[i]&1)!=1){
                    events.add(tempArr[i]); //偶数数组
                }else{
                    odds.add(tempArr[i]); //奇数数组
                }
            }
            int[] eventsMatch=new int[events.size()];
            int result=0;
            //遍历奇数去匹配偶数
            for(int i=0;i<odds.size();i++){
                //每一步重新创建，也就是相当于清空
                int[] used=new int[events.size()];
                if(find(odds.get(i),events,used,eventsMatch)){
                    result++;
                }
            }
            System.out.println(result);
        }
    }
    public static boolean isPrime(int num) {
        for(int i = 2; i * i <= num; i++) {
            if(num % i == 0) {
                return false;
            }
            if(num == 1) {
                return false;
            }
        }
        return true;
    }
    public static boolean find(int x, ArrayList<Integer> evens,int[] used, int[] evensMatch) {
        //遍历偶数
        //去检查当前传入的奇数能否与偶数哪些数匹配
        for(int i = 0; i < evens.size(); i++) {
            //如果当前偶数与传入的奇数匹配，并且当前偶数位还没有匹配过奇数
            if(isPrime(x + evens.get(i)) && used[i] == 0) {
                //设置当前偶数位匹配为true，也就是 1
                used[i] = 1;
                //如果第i个偶数没有伴侣
                //或者第i个偶数原来有伴侣，并且该伴侣能够重新找到伴侣的话(这里有递归调用)
                //则奇数x可以设置为第i个偶数的伴侣
                //这里采用了匈牙利算法，能让则让
                if(evensMatch[i] == 0 || find(evensMatch[i], evens, used, evensMatch)) {
                    evensMatch[i] = x;
                    return true;
                }
            }
        }
        //遍历完偶数都没有可以与传入奇数做伴侣的，该奇数只能孤独终老了
        return false;
    }
}
